package Recursion;

import java.util.*;

/*BM55 没有重复项数字的全排列
* 给出一组数字，返回该组数字的所有排列*/
public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        // 存一种排列
        LinkedList<Integer> list = new LinkedList<>();
        // 递归进行
        backTrack(num,list);
        return res;
    }

    public void backTrack(int[] num, LinkedList<Integer> list){
        // 当list中的长度等于数组的长度，则证明此时已经找到一种排列了
        if(list.size() == num.length){
            // add进返回结果集中
            res.add(new ArrayList<>(list));
            return;
        }
        // 遍历num数组
        for(int i = 0; i < num.length; i++){
            // 若当前位置中的数已经添加过了则跳过
            if(list.contains(num[i]))
                continue;
            // 选择该数
            list.add(num[i]);
            // 继续寻找
            backTrack(num,list);
            // 撤销最后一个
            list.removeLast();
        }
    }





    /* 有重复项数字的全排列
    * 给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。*/
    public void recursion(ArrayList<ArrayList<Integer>> res, int[] num, ArrayList<Integer> temp, Boolean[] vis){
        //临时数组满了加入输出
        if(temp.size() == num.length){
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        //遍历所有元素选取一个加入
        for(int i = 0; i < num.length; i++){
            //如果该元素已经被加入了则不需要再加入了
            if(vis[i])
                continue;
            if(i > 0 && num[i - 1] == num[i] && !vis[i - 1])
                //当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过了
                continue;
            //标记为使用过
            vis[i] =  true;
            //加入数组
            temp.add(num[i]);
            recursion(res, num, temp, vis);
            //回溯
            vis[i] =  false;
            temp.remove(temp.size() - 1);
        }
    }
    //
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        //先按字典序排序
        Arrays.sort(num);
        Boolean[] vis = new Boolean[num.length];
        Arrays.fill(vis, false);
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> temp = new ArrayList<Integer>();
        recursion(res, num, temp, vis);
        return res;
    }

    /**
     * 判断岛屿数量
     * 解题思路:DFS与BFS
     * @param grid char字符型二维数组
     * @return int整型
     */
    public void dfs(char[][] grid, int i, int j) {
        int n = grid.length;
        int m = grid[0].length;
        // 置为0
        grid[i][j] = '0';
        //后续四个方向遍历
        if(i - 1 >= 0 && grid[i - 1][j] == '1')
            dfs(grid, i - 1, j);
        if(i + 1 < n && grid[i + 1][j] == '1')
            dfs(grid, i + 1,j);
        if(j - 1 >= 0 && grid[i][j - 1] == '1')
            dfs(grid, i, j - 1);
        if(j + 1 < m && grid[i][j + 1] == '1')
            dfs(grid, i, j + 1);
    }

    public int solve (char[][] grid) {
        int n = grid.length;
        //空矩阵的情况
        if (n == 0)
            return 0;
        int m = grid[0].length;
        //记录岛屿数
        int count = 0;
        //遍历矩阵
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                //遍历到1的情况
                if(grid[i][j] == '1'){
                    //计数
                    count++;
                    //将与这个1相邻的所有1置为0
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
   /*广度优先遍历*/
    public int solve2 (char[][] grid) {
        int n = grid.length;
        //空矩阵的情况
        if (n == 0)
            return 0;
        int m = grid[0].length;
        //记录岛屿数
        int count = 0;
        //遍历矩阵
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                //遇到1要将这个1及与其相邻的1都置为0
                if(grid[i][j] == '1'){
                    //岛屿数增加
                    count++;
                    grid[i][j] = '0';
                    //记录后续bfs的坐标
                    Queue<Integer> q1 = new LinkedList<Integer>();
                    Queue<Integer> q2 = new LinkedList<Integer>();
                    q1.offer(i);
                    q2.offer(j);
                    //bfs
                    while(!q1.isEmpty()){
                        int row = q1.poll();
                        int col = q2.poll();
                        //四个方向依次检查：不越界且为1
                        if(row - 1 >= 0 && grid[row - 1][col] == '1'){
                            q1.offer(row - 1);
                            q2.offer(col);
                            grid[row - 1][col] = '0';
                        }
                        if(row + 1 < n && grid[row + 1][col] == '1'){
                            q1.offer(row + 1);
                            q2.offer(col);
                            grid[row + 1][col] = '0';
                        }
                        if(col - 1 >= 0 && grid[row][col - 1] == '1'){
                            q1.offer(row);
                            q2.offer(col - 1);
                            grid[row][col - 1] = '0';
                        }
                        if(col + 1 < m && grid[row][col + 1] == '1'){
                            q1.offer(row);
                            q2.offer(col + 1);
                            grid[row][col + 1] = '0';
                        }
                    }
                }
            }
        }
        return count;
    }
    /*字符串的排列:如果没重复的,这样写就可以,*/
    public ArrayList<String> Permutation1(String str) {
        ArrayList<String> arrayList=new ArrayList<>();
        LinkedList<Character> list = new LinkedList<>();
        PermutationFunc1(arrayList,str,list);
        return arrayList;

    }



    private  void PermutationFunc1(ArrayList<String> arrayList, String str, LinkedList<Character> list){

        if (list.size() == str.length()){
            String ret="";
            for (char ch:list) {
                ret+=ch;
            }
            arrayList.add(ret);
        }
        for (int i = 0; i < str.length(); i++) {
            char ch=str.charAt(i);
            if (list.contains(ch)){
                //如果存在则跳过
                continue;
            }else {
                //不存在则加入
                list.add(ch);
                //继续遍历
                PermutationFunc1(arrayList,str,list);
                //删掉最后一个
                list.removeLast();
            }
        }
    }

    public void recursion(ArrayList<String> res, char[] str, StringBuffer temp, boolean[] vis){
        //临时字符串满了加入输出
        if(temp.length() == str.length){
            res.add(new String(temp));
            return;
        }
        //遍历所有元素选取一个加入
        for(int i = 0; i < str.length; i++){
            //如果该元素已经被加入了则不需要再加入了
            if(vis[i])
                continue;
            if(i > 0 && str[i - 1] == str[i] && !vis[i - 1])
                //当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了
                continue;
            //标记为使用过
            vis[i] = true;
            //加入临时字符串
            temp.append(str[i]);
            recursion(res, str, temp, vis);
            //回溯
            vis[i] = false;
            temp.deleteCharAt(temp.length() - 1);
        }
    }

    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<String>();
        if(str == null || str.length() == 0)
            return res;
        //转字符数组
        char[] charStr = str.toCharArray();
        // 按字典序排序
        Arrays.sort(charStr);
        boolean[] vis = new boolean[str.length()];
        //标记每个位置的字符是否被使用过
        Arrays.fill(vis, false);
        StringBuffer temp = new StringBuffer();
        //递归获取
        recursion(res, charStr, temp, vis);
        return res;
    }










}